<head>
    <meta charset="UTF-8">
<title>算法提高 Sheep</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p>信息技术的发展日益渗透到人类活动的各个领域。令人难以置信的是，最先进的科技被用到了农业上。</p>
<p>在一个大农场有一片草地和成群的羊。这里总共有 <i>n</i> 只羊，它们中的每一个被标上了一个独一无二的编号，编号的范围从 1 到 <i>n</i> &mdash;&mdash;因为你需要区分出每只羊并记住它们的信息，而且它们还如此的相似！这片草地有无限数量的区域，从 1 到无穷编号。已知 <i>i</i> 号羊喜欢编号从 <i>l<sub>i</sub></i> 到 <i>r<sub>i</sub></i> 的区域。</p>
<p>这里有两个牧羊人在照顾羊群：甲和乙。甲每天早晨起得很早，领着羊群到草地上去吃草。乙则在晚上出来领回所有的羊。</p>
<p>一天早晨，甲起得比平时有点迟，没有时间领羊群到草地上吃草。因此，他把所有有公共喜欢区域的羊拴在一起。甲认为这样会更好&mdash;&mdash;乙晚上时会少做些工作，因为羊不会走开太远，它们正被互相拴着呢！</p>
<p>到了夜晚，乙来到了草地，他把羊群聚集起来并尝试把它们排成一队。但是尽管他很努力了，羊群还是没有排成他想要的那样。乙没有力气和能力去解开羊群，只好让它们保持原样，但有一个条件：他想要把羊群排成一队，使得相互栓着的羊的最大距离尽可能小。两只羊的距离定义为它们在队列中排名的差值。</p>
<p>【输入格式】</p>
<p>第一行包含一个整数 <i>n</i>。接下来的 <i>n</i> 行每行包含两个整数 <i>l<sub>i</sub></i> 和 <i>r<sub>i</sub></i>。</p>
<p>【输出格式】</p>
<p>输出共一行，<i>n</i> 个用空格隔开的数字&mdash;&mdash;要求的羊群的排列。这一行的第 <i>i</i> 个值必须代表最优排列从左数第 <i>i</i> 只羊的编号。</p>
<p>如果有多种最优解，输出任意一种即可。</p>
<p>【样例输入】</p>
<p>3</p>
<p>1 3</p>
<p>5 7</p>
<p>2 4</p>
<p>【样例输出】</p>
<p>1 3 2</p>
<p>【样例输入】</p>
<p>5</p>
<p>1 5</p>
<p>2 4</p>
<p>3 6</p>
<p>1 7</p>
<p>2 6</p>
<p>【样例输出】</p>
<p>2 1 3 5 4</p>
<p>【样例输入】</p>
<p>4</p>
<p>1 3</p>
<p>4 6</p>
<p>5 7</p>
<p>2 3</p>
<p>【样例输出】</p>
<p>1 4 2 3</p>
<p>【数据规模和约定】</p>
<p>对于20%的数据，1 &le; <i>n</i> &le; 8；</p>
<p>对于60%的数据，1 &le; <i>n</i> &le; 200；</p>
<p>对于100%的数据，1 &le; <i>n</i> &le; 2000，1 &le; <i>l<sub>i</sub></i> &le; <i>r<sub>i</sub></i> &le; 10<sup>9</sup>。</p>